/*
 * perft.c
 *
 *  Created on: Apr 19, 2013
 *      Author: locpx
 */


#include <stdio.h>
#include "defines.h"
#include "extglobals.h"
#include "protos.h"

U64 perft(int ply, int depth)
{

	// Raw node count, up to depth, doing a full tree search.
	// perft is very similar to the search algorithm - instead of evaluating the leaves, we count them.
	//
	// Be carefull when calling this function with depths > 7, because it can take a very long
	// time before the result is returned: the average branching factor in chess is 35, so every
	// increment in depth will require 35x more computer time.
	//
	// perft is a good way of verifying correctness of the movegenerator and (un)makeMove,
	// because you can compare the results with published results for certain test positions.
	//
	// perft is also used to measure the performance of the move generator and (un)makeMove in terms
	// of speed, and to compare different implementations of generating, storing and (un)making moves.

	U64 retVal = 0;
	int i;

	// count this node
	if (depth == 0)
	{
		return 1;
	}

	// generate moves from this position
	board.moveBufLen[ply+1] = movegen(board.moveBufLen[ply]);

	// loop over moves:
	for (i = board.moveBufLen[ply]; i < board.moveBufLen[ply+1]; i++)
	{
		makeMove(board.moveBuffer[i]);
		{
			if (!isTwoKingsFaceToFace() && !isOtherKingAttacked())
			{
				// recursively call perft
				retVal += perft(ply + 1, depth-1);
			}
		}
		unMakeMove(board.moveBuffer[i]);
	}

	return retVal;
}
